package Sort;

public class sort3 {
    //选择排序
    public static void main(String[] args) {
        int[] arr = {10, 5, 21, 6, 7, 2, 9, 11, 3, 1};
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        choiceSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void choiceSort1(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
                int minindex = i;
            for (int j = i; j < arr.length; j++) {
                if(arr[j]<arr[minindex]){
                    minindex = j;
                }
            }
            swap(arr,minindex,i);
        }
    }

    public static void choiceSort2(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while(left<right){
            int minindex = left;
            int maxindex = left;
            for(int i = left+1;i<=right;i++){

                if(arr[i]<arr[minindex]){
                    minindex = i;
                }

                if(arr[i]>arr[maxindex]){
                    maxindex = i;
                }

            }
            swap(arr,left,minindex);
            //这里一定要注意如果maxindex本身就在left上，
            //那么此时最大值已被minindex换走
            if(maxindex==left){
                maxindex = minindex;
            }
            swap(arr,right,maxindex);

            left++;
            right--;

        }
    }

    public static void swap(int[] arr,int i,int j){
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }


}

